package com.mokairui.tree;

/**
 * @Description com.mokairui.tree
 * @Author Mokairui
 * @Since 2022/3/28
 */
public class BinaryTree<K extends Comparable<K>, V> {
    // 记录根节点
    private Node root;
    //记录树中元素的个数
    private int N;
    
    // 获取树中元素的个数
    public int size() {
        return N;
    }
    
    // 向树中添加元素 key -value
    public void put(K key, V value) {
        root = put(root, key, value);
    }
    
    // 向指定的树中添加 key - value, 并返回添加元素后新的树
    public Node put(Node x, K key, V value) {
        // 1.如果x子树为空
        if (x == null) {
            N++;
            return new Node(key, value, null, null);
        }
        // 2.如果x子树不为空
        // 比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            // 如果key大于x节点的键继续找x节点的右子树
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {
            // 如果key小于x节点的键继续找x节点的左子树
            x.left = put(x.left, key, value);
        } else {
            // 如果key等于x节点的键,则替换x节点的值value
            x.value = value;
        }
        return x;
    }
    
    // 查询树中指定key对应的value
    public V get(K key) {
        return get(root, key);
    }
    
    // 从指定的树x中, 查找key对应的值
    public V get(Node x, K key) {
        // x树为null
        if (x == null) {
            return null;
        }
        // x树不为null
        // 比较key和x节点的键的大小
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            // 如果key大于x节点的键,则继续找x节点的右子树
            return get(x.right, key);
        } else if (cmp < 0) {
            // 如果key小于x节点的键,则继续找x节点的左子树
            return get(x.left, key);
        } else {
            // 如果key等于x节点的键,就找到了键为key的节点
            return x.value;
        }
    }
    
    // 删除树中key对应的value
    public void delete(K key) {
        root = delete(root, key);
    }
    
    // 删除
    public Node delete(Node x, K key) {
        if (x == null) {
            return null;
        }

        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            // 如果key大于x节点的键,则继续找x节点的右子树
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            // 如果key小于x节点的键,则继续找x节点的左子树
            x.left = delete(x.left, key);
        } else {
            N--;
            // 如果key等于x节点的键,执行删除操作
            // 得到右子树中最小的节点
            if (x.right == null) {
                return x.left;
            }
            if (x.left == null) {
                return x.right;
            }
            
            // 找到右子树中最小的节点
            Node minNode = x.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            
            // 删除右子树中最小的节点
            Node n = x.right;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    // 变换n节点即可
                    n = n.left;
                }
            }
            
            // 让x节点的左子树成为minNode的左子树
            minNode.left = x.left;
            // 让x节点的右子树成为minNode的右子树
            minNode.right = x.right;
            // 让x节点的父节点指向minNode
            x = minNode;
        }
        return x;
    }
    
    // 找出树中最小的键
    public K min() {
        return min(root).key;
    }
    
    // 找出指定树中, 最小键所在的节点
    private Node min(Node x) {
        if (x.left != null) {
            return min(x.left);
        }
        return x;
    }
    
    // 找出树中最大的键
    public K max() {
        return max(root).key;
    }
    
    private Node max(Node x) {
        if (x.right != null) {
            return max(x.right);
        }
        return x;
    }
    
    // 节点类
    private class Node {
        // 存储键
        public K key;
        // 存储值
        private V value;
        // 记录左子节点
        public Node left;
        // 记录右子节点
        public Node right;

        public Node(K key, V value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
